WC2021 游记
杂
线上真·游记
T1 为什么就没找出来性质呢？CF 做太少了，思维模式太 low！T2 为什么模拟赛出现类似的还是不会呢？没弄懂！T3，T3 你推一半为什么不会了？这是真不会。。。
又 出 成 绩 了，28 + 60 + 20 = 108 铜，T1 挂了 4 分，然而就算没挂分也是差 6 分银牌（写了那好麻烦的 10 分就银了 /kel
dsy: 赛后算分，庸人自扰
差距没有很大，也没有缩小呢，xml 你要继续努力！
改题
括号路径
找性质的能力还是太菜了。。。我再不刷 CF 和 AT 我名字倒过来写！ 注意到这样的路径是双向的，而且若 (x, y) 是合法对，那么任意点 w 同时与 x、y 有或无路径。
即有合法路径的对形成的团中，两两互达！
类似「Joitter 交友」，缩就完事了。并查集维护连通性。记录每个点的出入括号，遇到同种类的就从了。合并点对采用启发式合并。人懒用了 map，两只 log。
表达式求值
magic breeding? Ah~ 加强版。每位显然是独立的。考虑二分的思想，$\geq lim$ 的为 $1$，$< lim$ 的为 $0$，那么 $\max$ 为取并，$\min$ 为取交。
括号很恶心，要建表达式树。我们选择从后往前建。叶子处是操作 id，非叶子处是 $($、$)$、$<$、$>$、$?$
本题要统计每个集合 $\geq$ 某种取值的方案数才能算出该取值在答案中贡献的次数。
集合只有 $2^m$ 种，取值却有 $nm$ 种。考虑 dp 预处理, 枚举集合表示这个集合里的数都 $\geq$ 那个值，$dp[x, 0/1]$ 表示在表达式树上 $x$ 节点的子树有多少种方案使得运算结果为 $0$/$1$。
表达式树是个二叉树。合并答案，记俩儿子 dp 值分别为 $(x0, x1)$, $(y0, y1)$，结果记为 $(z0, z1)$
- 对于 $>$: $z0 = x0 y0$, $z1 = x0 y1 + x1 y0 + x1 y1$
- 对于 $<$: $z0 = x0 y0 + x0 y1 + x1 y0$, $z1 = x1 y1$
- 对于 $?$: 上面两种加起来。
$O(2^m|E| + nm^2)$.
斐波那契
这道和「WC2020-猜数游戏」都先咕咕